Ma trận thưa
Ma trận thưa

Ma trận thưa

Trong giải tích sốkhoa học tính toán, một ma trận thưa (hay mảng thưa, tiếng Anh: sparse matrix hay sparse array) là một ma trận toán học mà trong đó đa số phần tử có giá trị là 0. Không có định nghĩa chặt chẽ bao nhiêu phần tử cần bằng 0 để ma trận được coi là thưa nhưng với một tiêu chí chung là số phần tử khác 0 phải xấp xỉ bằng số hàng hoặc các cột. Ngược lại, nếu ma trận không có nhiều các phần tử khác 0, thì ma trận đó được coi là đặc (dày, dầy). Số phần tử có giá trị bằng 0 chia cho tổng số phần tử (ví dụ, M x N với một ma trận có kích thước M x N) đôi khi gọi là tính thưa (sparsity) của ma trận.Về mặt khái niệm, sự thưa thớt tương ứng với các hệ thống có ít sự tương tác theo từng cặp. Ví dụ, một hàng người xếp hàng chờ mua đồ trước một cửa hàng ăn nhanh, mỗi người cách nhau 5 mét và không có tiếp xúc cơ thể với nhau thì đây được coi là một hệ thống thưa thớt. Ngược lại, nếu một hàng người này nắm tay nhau (hay đứng cách nhau cự ly gần hơn, khoảng 30 cm) thì được xem là một hệ thống dày đặc. Khái niệm thưa thớt rất hữu ích trong toán học tổ hợp và các lĩnh vực ứng dụng như lý thuyết mạnggiải tích số, thường có mật độ dữ liệu hoặc kết nối quan trọng thấp. Các ma trận thưa quy mô lớn thường xuất hiện trong các ứng dụng khoa học hay kỹ thuật khi giải quyết các vấn đề về phương trình vi phân riêng phần.Khi lưu trữ và thao tác với ma trận thưa trên máy tính, việc sử dụng các thuật toáncấu trúc dữ liệu chuyên dụng là điều hữu ích và thường cần thiết để tận dụng cấu trúc thưa thớt của ma trận.Trong lĩnh vực học máy, các máy tính chuyên dụng được tạo ra dành cho các ma trận thưa[1] rất phổ biến.[2] Các thuật toán và cấu trúc dữ liệu tiêu chuẩn dùng để thực hiện các phép tính với ma trận dày thường chậm và không hiệu quả khi áp dụng cho các ma trận thưa có kích thước lớn. Lý do là vì bộ nhớ máy tính buộc phải lãng phí tài nguyên khi lưu trữ các giá trị 0 xuất hiện tần suất cao trong ma trận thưa. Về bản chất, dữ liệu thưa sẽ được nén lại dễ dàng hơn và do đó giảm thiểu yêu cầu lưu trữ trên máy tính. Một số ma trận thưa có kích thước lớn không thể thực thi bằng các thuật toán tiêu chuẩn như đã làm với các ma trận dày.